import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test16 {
    /*
    定义一批作业
    （1）第一维度表示作业1,2,3
    （2）第二维度表示在机器1,还是机器2上运行的时间
     */
    int N = 3;//表示有三个作业需要调度
    int[][] jobs = {{2, 1}, {3, 1}, {2, 3}};
    boolean[] isJobsRun;
    int minTime = Integer.MAX_VALUE;//表示最小的运行时间
    int[] nowRun;//表示当前的机器的运行顺序
    int[] jobsRun;//表示最佳机器的运行顺序

    public void permute(int[][] jobs) {
        //1.初始化
        isJobsRun = new boolean[jobs.length];
        jobsRun = new int[jobs.length];
        nowRun = new int[jobs.length];
        Arrays.fill(nowRun, -1);
        //2.调用dfs(回溯的核心)
        dfs(0);
    }

    public void dfs(int t) {
        //当来到叶子节点后，就进行时间累加
        if (t == N) {
            int t1 = 0, t2 = 0, sum = 0;
            for (int x = 0; x < N; x++) {
                int i = nowRun[x];
        //一个作业在第2台机器上开始的时间，
        //是取决于上一个作业在机器2上完成的时间和自己本身在机器1上完成的时间的最大值
                t1 = t1 + jobs[i][0];
                t2 = Math.max(t1, t2) + jobs[i][1];
                //sum就是在累加没一个作业最后再机器2上完成的时间和
                sum += t2;
            }
            int tmpTime = minTime;//用来判断是否有最小值的改变
            minTime = Math.min(minTime, sum);
            //如果两者不相等，正面值有进行改变
            if (tmpTime != minTime) {
                //将本次的机器运转顺序记录下来
                for (int i = 0; i < N; i++) {
                    jobsRun[i] = nowRun[i] + 1;
                }
            }
        }
        //如果
        else {
            //每次都从第一个机器开始看起
            for (int i = 0; i < N; i++) {
                //证明这个作业没被选择
                if (isJobsRun[i] == false) {
                    //把这个作业标记为已选择
                    isJobsRun[i] = true;
                    //因为下标是从0开始，所以第1个作业就是 0 ;
                    nowRun[t] = i;
                    dfs(t + 1);
                    //恢复现场
                    isJobsRun[i] = false;
                    nowRun[t] = -1;
                }
            }
        }
    }

    public static void main(String[] args) {
        Test16 test16 = new Test16();
        test16.permute(test16.jobs);
        System.out.println("批处理作业调度的最小时间和：" + test16.minTime);
        System.out.print("顺序为：");
        for(int i = 0;i < test16.N;i++){
            System.out.print(test16.jobsRun[i] + " ");
        }
    }
}
